﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks.Dataflow;

namespace Corecalc
{
    public abstract class GRParent
    {
        public GRParent Parent { get; set; }
    }

    public class GRGraph : GRParent
    {
        public GRNode Root { get; set; }
        public List<GRNode> Nodes { get; set; }
        public List<CellAreaNode> Cans { get; set; }

        public GRGraph() {
            Cans = new List<CellAreaNode>();
            Nodes = new List<GRNode>();
        }

        public double Ft { get; set; }                  //Sum of Ft for all nodes in the graph
        public double CP { get; set; }                  //Critical Path value for entire graph
        public double F { get { return 1; } }           //Number of times this graph is executed

        public List<GRNode> GetInputEdges() {
            List<GRNode> inputEdges = new List<GRNode>();
            foreach (GRNode node in Nodes) {
                foreach (GRNode input in node.InputEdges) {
                    if (input.Parent != node.Parent) {

                        if (input.Host == node.Host) {
                            throw new Exception("");
                        }
                        
                        
                        inputEdges.Add(input);
                    }
                }
            }
            return inputEdges;
        }
    }

    public abstract class GRNode : GRParent
    {
        public List<GRNode> InputEdges { get; set; }
        public List<GRNode> OutputEdges { get; set; }
        public FullCellAddr Host { get; set; }
        public bool DFSVisited { get; set; }

        public double CP { get; set; }
        public virtual double Ft { get; set; }
        public virtual double T_in { get; set; }
        public virtual double T_out { get; set; }
        public Task Task { get; set; }
        public Task TempTask { get; set; }

        public double Value { get; set; }

        public GRNode() {
            InputEdges = new List<GRNode>();
            OutputEdges = new List<GRNode>();
        }

        public abstract double Eval();

        public void DepthFirstSearch(Action<GRNode> f) {
            List<GRNode> nodes = new List<GRNode>();

            Stack<GRNode> stack = new Stack<GRNode>();
            stack.Push(this);
            while (stack.Count > 0) {
                GRNode node = stack.Pop();
                if (!node.DFSVisited) {
                    node.DFSVisited = true;
                    f(node);
                    nodes.Add(node);

                    foreach (GRNode input in node.OutputEdges)
                        stack.Push(input);
                }
            }

            foreach (GRNode node in nodes)
                node.DFSVisited = false;
        }

        public override string ToString() {
            return string.Format("{0}, Fca: {1}", GetType(), Host);
        }
    }

    abstract public class SimpleNode : GRNode
    {

    }

    public abstract class CompoundNode : GRNode
    {
        public List<GRGraph> Graphs { get; set; }
        
        public CompoundNode() {
            Graphs = new List<GRGraph>();
        }

        public abstract List<GRNode> ContainedNodes();

        //Called from AssignCosts instead of summing over Ft values of all nodes as in the pseudocode
        public abstract double ComputeFt();
    }

    public abstract class ParallelNode : GRNode
    {
        public GRGraph Graph { get; set; }

        public double F { get; set; }
        public int Size { get; set; }
    }

    public class BinopNode : SimpleNode
    {
        public string Operator { get; set; }
        public GRNode Left { get; set; }
        public GRNode Right { get; set; }

        public BinopNode(string op, GRNode[] args) {
            Operator = op;
            Left = args[0];
            Right = args[1];

            if (!(args[0] is ConstNode)) {
                InputEdges.Add(Left);
                Left.OutputEdges.Add(this);
                T_in += Left.T_out;
            }

            if (!(args[1] is ConstNode)) {
                InputEdges.Add(Right);
                Right.OutputEdges.Add(this);
                T_in += Right.T_out;
            }

            Ft = MPModel.GetExecutionTime(op);
            T_out = MPModel.GetCommunicationCost("double");     //Only holds for +, -, < etc..
        }

        public Func<double, double, double> GetApplier() {
            switch (Operator) {
                case "+": return (x, y) => x + y;
                case "-": return (x, y) => x - y;
                case "*": return (x, y) => x * y;
                case "/": return (x, y) => x / y;
                case ">": return (x, y) => x > y ? 1.0 : 0.0;
                case "<": return (x, y) => x < y ? 1.0 : 0.0;
                case ">=": return (x, y) => x >= y ? 1.0 : 0.0;
                case "<=": return (x, y) => x <= y ? 1.0 : 0.0;
                default: throw new System.NotImplementedException();
            }
        }

        public override double Eval() {
            var applier = GetApplier();
            double left, right;

            if (Left == null && Right == null) {
                left = InputEdges[0].Eval();
                right = InputEdges[1].Eval();
            } else if (Left != null & Right != null) {
                left = Left.Eval();
                right = Right.Eval();
            } else if (Left != null && Right == null) {
                left = Left.Eval();
                right = InputEdges[0].Eval();
            } else if (Left == null && Right != null) {
                left = InputEdges[0].Eval();
                right = Right.Eval();
            } else {
                throw new Exception("Uh oh..");
            }

            Value = applier(left, right);
            return Value;
        }
    }

    public delegate double FApplier(List<GRNode> inputArgs);

    public class BuiltInFunctionCallNode : SimpleNode
    {
        public static Dictionary<string, FApplier> functions;

        public string Name { get; set; }
        public bool Par { get; set; }
        public List<GRNode> FormulaArgs { get; set; }
        public List<ConstNode> ConstArgs { get; set; } 

        static BuiltInFunctionCallNode() {
            functions = new Dictionary<string, FApplier>();
            functions.Add("SUM", args => {
                var evalArgs = args.ConvertAll(arg => arg.Eval());
                return evalArgs.Sum();
            });
            functions.Add("AVERAGE", args => {
                var evalArgs = args.ConvertAll(arg => arg.Eval());
                return evalArgs.Average();
            });
            functions.Add("SIN", args => {
                Debug.Assert(args.Count == 1);
                return Math.Sin(args[0].Eval());
            });
            functions.Add("COS", args => {
                Debug.Assert(args.Count == 1);
                return Math.Cos(args[0].Eval());
            });
            functions.Add("SQRT", args => {
                Debug.Assert(args.Count == 1);
                return Math.Sqrt(args[0].Eval());
            });
        }

        public BuiltInFunctionCallNode(string name, GRNode[] args) {
            Name = name;
            FormulaArgs = new List<GRNode>();
            ConstArgs = new List<ConstNode>();

            foreach (GRNode arg in args) {
                InputEdges.Add(arg);
                arg.OutputEdges.Add(this);
            }

            //ExecutionTimeCost is set by InitCalls
            T_in = args.Sum(arg => arg.T_out);
            T_out = MPModel.GetCommunicationCost("double");   //Should depend on the concrete function that is called

            Debug.Assert(name.Equals("AVERAGE") || name.Equals("SUM") || name.Equals("COS") || name.Equals("SIN") || name.Equals("SQRT"));
        }

        public override double Eval() {
            List<GRNode> ns = FormulaArgs;
            ns.AddRange(ConstArgs);
            Value = functions[Name](ns);
            return Value;
        }
    }

    public class IfNode : CompoundNode
    {
        public IfNode(GRNode cond, GRGraph @true, GRGraph @false) {
            InputEdges.Add(cond);
            cond.OutputEdges.Add(this);

            Graphs.Add(@true);
            Graphs.Add(@false);

            //Ft for IF-/Compound Nodes are set in AssignCosts
            T_in = cond.T_out + Math.Max(@true.GetInputEdges().Sum(e => e.T_out), @false.GetInputEdges().Sum(e => e.T_out));
            T_out = Math.Max(Graphs[0].Root.T_out, Graphs[1].Root.T_out);
        }

        public override double Eval() {
            int branch = InputEdges[0].Eval() > 0 ? 1 : 0;
            Value = Graphs[branch].Root.Eval();
            return Value;
        }

        public override List<GRNode> ContainedNodes() {
            var nodes = new List<GRNode>();
            nodes.AddRange(Graphs[0].Nodes.OfType<CompoundNode>().SelectMany(n => n.ContainedNodes()));
            nodes.AddRange(Graphs[1].Nodes.OfType<CompoundNode>().SelectMany(n => n.ContainedNodes()));
            nodes.AddRange(Graphs[0].Nodes);
            nodes.AddRange(Graphs[1].Nodes);
            return nodes;
        }

        //Called from AssignCosts to assign execution time costs to compound nodes
        //At this point, AssignCosts should have assigned Ft values to both subgraphs
        public override double ComputeFt() {
            return Math.Max(Graphs[0].Ft, Graphs[1].Ft);
        }
    }

    public class ConstNode : SimpleNode
    {
        public Const Const { get; set; }

        public ConstNode(Const @const, FullCellAddr fca) {
            Const = @const;

            Ft = MPModel.GetExecutionTime("const");
            T_in = 0.0;
            T_out = Const.CommunicationCost(fca);
        }

        public override double Eval() {
            NumberValue v = Const.Eval(Host.sheet, Host.ca.col, Host.ca.row) as NumberValue;
            Value = v.value;
            return Value;
        }
    }

    public class CellRefNode : SimpleNode
    {
        public Cell Cell { get; set; }      //Non-null if not part of the support graph
        
        public CellRefNode(GRNode node) {
            InputEdges.Add(node);
            node.OutputEdges.Add(this);

            Ft = MPModel.GetExecutionTime("cellref");
            T_out = T_in = node.T_out;
        }

        //This constructor does not set the "Host" field, fca only required for communication cost lookup
        public CellRefNode(Cell cell, FullCellAddr fca) {
            Cell = cell;

            Ft = MPModel.GetExecutionTime("cellref");
            T_out = T_in = MPModel.GetCommunicationCost(cell, fca);
        }

        public override double Eval() {
            if (InputEdges.Count() == 1) {
                Value = InputEdges[0].Value;
                return Value;
            } else {
                NumberValue v = Cell.Eval(Host.sheet, Host.ca.col, Host.ca.row) as NumberValue;
                Value = v.value;
                return Value;
            }
        }
    }

    public class CellAreaNode : SimpleNode
    {
        private List<ConstNode> ConstNodes { get; set; }
        private List<GRNode> FormulaNodes { get; set; }

        public CellAreaNode(List<GRNode> formulaNodes, List<ConstNode> constNodes)
        {
            ConstNodes = constNodes;
            FormulaNodes = formulaNodes;
            foreach (var node in formulaNodes) {
                InputEdges.Add(node);
                node.OutputEdges.Add(this);
            }

            Ft = MPModel.GetExecutionTime("cellref") * formulaNodes.Count;
            T_out = T_in = formulaNodes.Sum(n => n.T_out);
        }

        public override double Eval() {
            throw new System.NotImplementedException();
        }

        public void RemoveFromGraph() {
            Debug.Assert(OutputEdges.Count == 1 && OutputEdges[0] is BuiltInFunctionCallNode);
            foreach (GRNode outputEdge in OutputEdges) {
                outputEdge.InputEdges.Remove(this);
                foreach (GRNode inputEdge in InputEdges) {
                    outputEdge.InputEdges.Add(inputEdge);
                }
                var n = outputEdge as BuiltInFunctionCallNode;
                n.ConstArgs = ConstNodes;
                n.FormulaArgs = FormulaNodes;
            }

            foreach (GRNode inputEdge in InputEdges) {
                inputEdge.OutputEdges.Remove(this);
                foreach (GRNode outputEdge in OutputEdges) {
                    inputEdge.OutputEdges.Add(outputEdge);
                }
            }

            (Parent as GRGraph).Nodes.Remove(this);
        }
    }

    public class Utils
    {
        public static List<A> TopSort<A>(IEnumerable<A> items, Func<A, IEnumerable<A>> outgoing) {
            List<A> sortedList = new List<A>();
            List<A> marked = new List<A>();
            List<A> tempMarked = new List<A>();

            Action<A> visit = null;
            visit = n => {
                if (tempMarked.Contains(n)) throw new Exception("Uh oh..!!");
                if (!marked.Contains(n)) {
                    tempMarked.Add(n);

                    var o = outgoing(n);
                    foreach (A m in o)
                        visit(m);

                    marked.Add(n);
                    tempMarked.Remove(n);
                    sortedList.Add(n);      //Should've been AddFirst, we reverse the list instead
                }
            };

            Queue<A> unmarked = new Queue<A>(items);
            while (unmarked.Count > 0) {
                A n = unmarked.Dequeue();
                visit(n);
            }

            sortedList.Reverse();
            return sortedList;
        }
    }

    public class TestInput
    {
        public double TSched { get; set; }
        public double TMin { get; set; }
        public double Rc { get; set; }
        public double Wc { get; set; }
        public int Pc { get; set; }
    }

    public class PartitioningResult
    {
        public int TaskCount { get; set; }
        public Dictionary<int, int> NodesInTasks { get; set; }
        public double BuildSecs { get; set; }
        public double PartitioningSecs { get; set; }
        public double GraphCPBefore { get; set; }
        public double GraphCPAfter { get; set; }
        public Partition Partition { get; set; }
    }
}
